#define DEBUG
#include <cstdio>

using namespace std;

const int maxk=9, mods=990804011;

class DigitalSystem {
public:
  int n;
  long long p[maxk+1], a[maxk+1];

  void init(int k, long long *x) {
    n = k;
    p[0] = 1;
    for (int i=1; i<=k; i++) {
      a[i] = x[i]+1;
      p[i] = p[i-1]*a[i];
    }
  }

  void toArray(long long o, long long *ans) {
    for (int i=1; i<=n; i++) {
      ans[i] = o/p[i-1]%a[i];
    }
  }

  long long toNum(long long *o) {
    long long ret=0;
    for (int i=1; i<=n; i++) {
      ret += o[i]*p[i-1];
    }
    return ret;
  }
};

int main() {
  freopen("c.in", "r", stdin);
  freopen("c.out", "w", stdout);

  int t;
  scanf("%d", &t);
  for (int ti=1; ti<=t; ti++) {
    static long long l[maxk+1], r[maxk+1];
    int k;
    scanf("%d", &k);
    for (int i=1; i<=k; i++) {
      scanf("%lld %lld", l+i, r+i);
    }

    if (k==1) {
      printf("%lld\n", (r[1]-l[1]+1)%mods);
      continue;
    }

    static DigitalSystem sys;
    static long long f[1000000+1];
    sys.init(k, r);

    long long ans=0;
    for (int i=0; i<sys.p[k]; i++) {
      static long long temp[maxk+1];
      sys.toArray(i, temp);
      bool one=true, addToAns=true;
      for (int j=1; j<=k; j++) {
	if (!temp[j]) {
	  f[i] = 0;
	  break;
	} else if (temp[j]!=1) {
	  one = false;
	  temp[j]--;
	  f[i] = (f[i]+f[sys.toNum(temp)])%2;
	  temp[j]++;
	}
	if (temp[j]<l[j] || temp[j]>r[j]) {
	  addToAns = false;
	}
      }
      if (one) {
	f[i] = 1;
      }
      if (addToAns) {
	ans = (ans+f[i])%mods;
      }
    }
    printf("%lld\n", ans);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
